\subsection{Alias Analysis Component}
The accuracy of the data structure randomization still suffers
pointer alias problem, for example, the pointer may point to certain
data structure instance, if the data structure instance is
randomized, the pointer may access the instance according to its own
different type and lead to the memory inconsistency. We introduce
the de-randomization and re-randomization method in the Section 3.5
and Section 3.6, the main idea is when there is the pointer with
type casting pointing to the data structure instance, we
de-randomize the data structure instance, after the pointer to the
instance is free, we re-randomize it again. To guarantee the
accuracy of the data structure randomization, we introduce the alias
analysis component which computes the pointer set that points to the
same data structure instance. SALADS extends the call strings and
liveness analysis of gcc-4.6.0 and is context-sensitive,
flow-sensitive, field-insensitive.

\begin{figure*}[t]
\centering
\includegraphics[scale=0.8]{Example1.eps}
\caption{Data Structure Alias Analysis } \label{fig:example1}
\end{figure*}


The SALADS pointer analysis has three feature compared with the one
of gcc-4.6.0. First, we use the strong liveness information to
eliminate the redundant points-to information. Second, we calculate
the musts-points-to information instead of using may-points-to
information, which makes the points-to information more precise.
Third, we use value-based termination of call strings during
interprocedural analysis which reduces the number of call strings
sharply.

Figure~\ref{fig:example1} provides a motivating example for our
alias analysis. In the example, there are a global data structure
instance \texttt{TEST p} (Line 9 in Figure~\ref{fig:example1}(a))and
two pointers \texttt{int * x} and \texttt{int * y} (Line 10 and 23
in Figure~\ref{fig:example1}(a)). The memory space of \texttt{p} can
be accessed by either the \texttt{p} itself or the pointer
\texttt{x} and \texttt{y}. According to our data structure
randomization method in Section 3.4 and 3.5, we will randomize the
data structure instance at the statement \texttt{p.a=1} (Line 14 in
Figure~\ref{fig:example1}(a)) and will de-randomize it at statement
\texttt{x=(int *) \&p} (Line 15 in Figure~\ref{fig:example1}(a))
since there is the type casting between \texttt{x} and \texttt{p}.
The alias analysis will help us to find the point when can we
re-randomize the data structure \texttt{p}.

Figure~\ref{fig:example1}(b) shows the work flow of the program
listed in Figure~\ref{fig:example1}(a), the node of the work flow
represents the statement in the program. \texttt{c1} and \texttt{r1}
represents the call statement and return statement of the func()
(Line 17 in Figure~\ref{fig:example1}(a)). Based on the work flow,
first, we need to calculate the strong liveness information of the
pointer. The strong liveness information is the pointer which is
directly used or used indirectly to define the pointers that are
strong live. We calculate the strong liveness information using the
backwards data flow analysis. For example, as shown in
Figure~\ref{fig:example1}(b), \texttt{y} is strong live at node 10,
then we propagate this information to its previous node, including
node 7, 8 and 9, we stop to propagate the information at node 7
since the node is used to define the pointer \texttt{y}. At the same
node 7, since \texttt{y} is strong live, so \texttt{x} is strong
live since it indirectly defines \texttt{y}. We further propagate
the information that \texttt{x} is strong live to previous nodes,
including nodes 3-6. We stop the liveness information propagation at
node 3 because \texttt{x} is defined by node 3. Note that the
liveness information is empty at nodes 11-14, because the pointers
\texttt{x} and \texttt{y} are not used any more. The liveness
information is shown on the left of the node in
Figure~\ref{fig:example1}(c). Second, based on the points-to
information at node 3 (x,p) and node 7 (y,x), we combine the
liveness information to calculate the musts-points-to information.
The musts-points-to information is shown on the right hand of the
node in Figure~\ref{fig:example1}(c). Note that we only propagate
the musts-points-to information rather than may-points-to
information in original gcc. The musts-points-to information only
calculates the point is liveness, and the points-to information must
reach the node on the control flow graph, instead, the may-points-to
information calculates all the possible cases regardless the
information flows to the node in the control flow graph or the
pointer is liveness. As such our method can generate more precise
points-to information than the original one. Third, we do the
interprocedural points-to information propagation, during this
process, flow and context-sensitivity data flow analysis is
performed by using value-based termination \cite{CC08} of call
strings instead of constructing prescribed length of the call
strings.
